213. 打家劫舍 II

Similar Question

Solution Tips

方案一: 动态规划

Since House[1] and House[n] are adjacent, they cannot be robbed together. Therefore, the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the House Robber, which is already been solved.

var rob = function(nums) {
    // 1. 定义 dp[i] 为偷前 i 家, 能获得最大价值
    // 与 1 最大区别就是围成了一圈, 要不从两边同时开始偷 ? 这样参考对撞指针, 相撞了就可以判断?
    // 又或者在最后一个的时候, 判断一下? 如果是第 0 家已经偷过了, 就不能偷了

    const dp = Array.from({ length: nums.length }, () => 0);
    if (nums.length === 1) {
        return nums[0];
    }
    dp[0] = nums[0];
    // 一定偷第一家
    dp[1] = nums[0];
    for (let i = 2; i < nums.length; i++) {
        // 根据 dp[i] 的定义, 如果不偷这一家的收益更大, 那么就不应该偷的
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    dp[nums.length - 1] = dp[nums.length - 2];
    // 到目前为止都是和 1 相同的, 在最后这里做一个特判
    // 因为 dp[-1] 肯定是没有影响的, 只需要考虑 dp[0], 就行了
    // 可以走两圈, 一圈是不偷第一家, 这样最后一家就肯定可以偷了
    // 第二圈是偷第一家, 这样最后一家就肯定不偷, 最后一家不偷, 那就是 dp[-2]

    console.log(dp.concat());

    const dp2 = Array.from({ length: nums.length }, () => 0);
    if (nums.length === 1) {
        return nums[0];
    }
    // 不偷第一家
    dp2[0] = 0;
    dp2[1] = nums[1];
    for (let i = 2; i < nums.length; i++) {
        // 根据 dp2[i] 的定义, 如果不偷这一家的收益更大, 那么就不应该偷的
        dp2[i] = Math.max(nums[i] + dp2[i - 2], dp2[i - 1]);
    }
    console.log(dp2.concat());
    // return dp[0] > dp[1] ? dp[nums.length - 2] : dp[nums.length - 1];
    return Math.max(dp[nums.length - 1], dp2[nums.length - 1]);
};
// console.log(rob([2,3,2]));
console.log(rob([1,2,3]));

方案一: 优化

var rob = function(nums) {
    const length = nums.length;
    if (length === 1) {
        return nums[0];
    } else if (length === 2) {
        return Math.max(nums[0], nums[1]);
    }
    return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
};

const robRange = (nums, start, end) => {
    let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
    for (let i = start + 2; i <= end; i++) {
        const temp = second;
        second = Math.max(first + nums[i], second);
        first = temp;
    }
    return second;
}